Stack & Queue

스택과 큐는 Delete 연산에 의한 집합에서 삭제되는 원소가 미리 결정되는 동적 집합이다.
스택은 가장 최근에 삽입된 원소가 삭제된다. ; 후입선출(LIFO)
큐는 가장 오래된 원소가 삭제된다. ; 선입선출(FIFO)
스택(Stack)
스택에서는 Insert 연산을 Push, Delete 연산을 Pop이라고 부른다.
#include <iostream>
#include <cstdio>
using namespace std;
template <typename T>
struct Stack{
T* data;
int size, top=-1;
Stack(int _size): size(_size){
if(size>0){
data=new T[size];
}
}
~Stack(){
delete[] data;
}
bool empty(void){
if(this->top==-1) return true;
else return false;
}
void push(T x){
this->top++;
if(this->top==this->size-1){
perror("Stack Overflow");
exit(1);
} else {
this->data[this->top]=x;
}
}
T pop(void){
if(this->empty()){
perror("Stack Underflow");
exit(1);
} else {
this->top--;
return this->data[this->top+1];
}
}
};
int main(void){
Stack<int> stack(10);
stack.push(10);
stack.push(5);
stack.push(1);
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
return 0;
}
큐(Queue)
스택에서는 Insert 연산을 Enqueue, Delete 연산을 Dequeue이라고 부른다.
#include <iostream>
#include <cstdio>
using namespace std;
template <typename T>
struct Queue{
int tail=0, head=0, size, occ=0;
T* data;
Queue(int _size): size(_size) {
data=new T[size];
}
~Queue(){
delete[] data;
}
bool empty(void){
if(this->head==this->tail) return true;
else return false;
}
void enqueue(T x){
if(this->occ==this->size){
perror("Queue Overflow");
exit(1);
} else {
this->data[this->tail]=x;
if(this->tail==this->size-1) this->tail=0;
else this->tail++;
occ++;
}
}
T dequeue(void){
if(this->occ==0){
perror("Queue Underflow");
exit(1);
} else {
int x=this->data[this->head];
if(this->head==this->size-1){
this->head=0;
} else {
this->head++;
}
occ--;
return x;
}
}
};
int main(void){
Queue<int> queue(5);
queue.enqueue(10);
queue.enqueue(5);
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(6);
cout<<queue.dequeue()<<'\n';
cout<<queue.dequeue()<<'\n';
cout<<queue.dequeue()<<'\n';
cout<<queue.dequeue()<<'\n';
cout<<queue.dequeue()<<endl;
return 0;
}